In digital image processing, it is sometimes desirable to separate some form of structure from a background in a digital image. This can be achieved by so-called thresholding or binarization, in which the luminance values of the pixels of the digital image are compared to a threshold value. More particularly, luminance values above the threshold value are set to 1, while luminance values below the threshold value are set to 0, or vice versa. With a well-selected threshold value, the thresholding results in a binary image with defined, real structures.
In many cases, a sequence of images is processed in a number of steps. One of the introductory steps can be the above-mentioned thresholding, which aims on the one hand to locate relevant structures and, on the other, to reduce the amount of data that is processed in subsequent steps. Of course, it is desirable for the thresholding to be carried out with high precision, as errors will otherwise propagate in the subsequent processing steps.
It its simplest form, the thresholding means that the luminance value of each pixel in a current image is compared with a global threshold value. Such so-called global thresholding requires, however, extensive control of the image recording so as to avoid luminance variations and noise. In practical applications there are often variations within each image, for example with regard to the background luminance, signal-to-noise ratio and sharpness. With global thresholding such variations can lead to structures being missed or to fictitious structures being identified, particularly at the periphery of the images.
In order to solve these problems, so-called local thresholding is used, in which a threshold value is calculated for each pixel in an image on the basis of the luminance values of the surrounding pixels. This is, however, a time-consuming operation that, in addition, requires intermediate storage of the digital image.
An example where the above considerations arise is in calculating a position based on images of a pattern on a base. The pattern contains individual symbols, the shape and/or relative location of which code said position. The images can, for example, be recorded optically by a sensor in a hand-held apparatus, for example in the form of a pen. Such a pen for position determination is described, for example, in U.S. Pat. No. 5,051,736, U.S. Pat. No. 5,477,012 and WO 00/73983 and can be used to record handwritten information digitally.
The above-mentioned images can be processed in a data processing unit, such as a suitably programmed microprocessor, an ASIC, an FPGA, etc, which receives a sequence of digital grayscale images, converts these to binary for identification of the above-mentioned symbols, and calculates a position on the basis of each binarized image. During the binarization, a threshold matrix is used that contains a threshold value for each pixel in the grayscale image. The recording of handwritten information should be carried out at high temporal resolution, typically approximately 50–100 images per second, for which reason it is difficult to combine the requirements for high precision in the thresholding with the require-ments for rapid processing and small memory requirement, even in a specially-adapted data processing unit.
In the article “Threshold Selection Based on a Simple Image Statistic”, published in 1985 in the periodical Computer Vision, Graphics and Image Processing, No. 30, pp 125–147, examples are given of various local thresholding methods. One such method is based on the fact that an adequate threshold value can be calculated based on a derivative value for each pixel in the original grayscale image. More particularly, a derivative matrix is calculated by convolution of the grayscale image with a suitable derivative mask, whereupon the pixel values of the derivative matrix are multiplied by the pixel values of the grayscale image to create a product matrix. Thereafter the derivative matrix and the product matrix are divided into subareas, within which a respective sum of the pixel values is calculated. Finally, local threshold values are obtained for the various subareas from the quotient between the subarea sums for the product matrix and the derivative matrix. The method is, however, time-consuming, among other things as a result of the calculation of the derivative matrix by convolution and the calculation of the threshold matrix by division. The method is also undesirably memory-intensive, as it requires the intermediate storage of the grayscale image, the derivative matrix and the product matrix.
U.S. Pat. No. 5,764,611 describes a thresholding method to be applied to grayscale images containing a pattern of dark dots against a bright background. In this method, the grayscale image is divided into subareas, within which the pixel values are summed to create a sum matrix. A low-pass filter is then applied to this sum matrix to create a background matrix, which after multiplication by a suitable fraction value is considered to form a matrix of local threshold values. In addition to a time-consuming low-pass filtering, this thresholding method is hampered by being sensitive to lack of sharpness in the grayscale image. Such lack of sharpness must be eliminated by extensive pre-processing of the grayscale image. This is achieved by high-pass filtering of the incoming grayscale image, whereupon the resulting luminance values are summed within the above-mentioned subareas to create a contrast matrix. The contrast matrix is then used to produce coefficients for a subarea-specific contrast function, which is finally allowed to operate on the grayscale image in order to eliminate the lack of sharpness in the same. This pre-processing comprises several time-consuming operations and is, in addition, memory-intensive in that it requires the intermediate storage of both the grayscale image and the result of the high-pass filtering.
Prior-art technique also includes U.S. Pat. No. 4,593,325, which describes a method for adaptive thresholding of a grayscale image prior to binary duplication of the same.